package com.company.algo.niuke;

import java.util.HashSet;
import java.util.Set;

/**数组中的最长连续子序列【字节，不会啊】
给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 3,4,5,6为连续的自然数）
 解法：hash表+并查集思想(找祖先)
 https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/zui-chang-lian-xu-xu-lie-by-leetcode-solution/
 */
public class MLS {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i: nums) set.add(i);
        int res = 1;
        for(int num: nums){
            if (!set.contains(num-1)){//只有当前num不属于某个连续子序列时，才开始搜索祖先
                int cur = num;
                int count = 1;
                while (set.contains(cur+1)){
                    cur = cur+1;
                    count++;
                }
                res = Math.max(res,count);
            }
        }
        return res;
    }
}
